package aco;

import java.awt.*;
import java.util.ArrayList;

// 算法要解的问题都在此类的对象中
// VRPTW中的内部类 Problem，记录每个时域要解决的问题
public class VRPTW {
    // maximum number of vehicle allowed for constructing the solution or the size of the vehicle fleet
    private int noVehicles;

    // the capacity of each vehicle
    private int capacity;

    /* 表示除仓库外，所有的城市数量。number of cities/customers, except the depot */
    static int n;

    // 存储所有城市请求（包括动态和静态）仓库为0，城市编号从1开始
    // arraylist which keeps all the customer requests defined in the VRPTW instance
    private ArrayList<Request> requests;

    // 当前可访问城市（已经出现的城市请求，且还未被锁定）城市编号从0开始数，不包括仓库
    //arraylist which keeps the ids of the available requests known at the current time
    //initially it contains the ids of the apriori requests, having available time = 0
    private ArrayList<Integer> idAvailableRequests;

    // 动态请求城市的链表（随着时间进行，从此链表中动态抽取请求城市）仓库为0，城市编号从1开始
    //arraylist which keeps the list of dynamic requests, which are not known in advance, having available time > 0
    private ArrayList<Request> dynamicRequests;

    // 城市的坐标
    static class Point {
        double x;
        double y;
    }

    // 这应该就不是代表单个时域，仅仅是为了存储一些不变的东西
    // 静态类可以存储一些不随对象而发生改变的东西
    public static class Problem {
        String name; /* instance name */
        Point[] nodes; /* array of classes containing coordinates of nodes */
        double[][] distance; /* distance matrix: distance[i][j] gives distance，i->j的距离 */

        /* candidate list */
        /*下面是邻近城市链表。nn_list不包括仓库，nn_list_all包括仓库。nn_list[i][j]表示到城市i距离第j近的城市编号 */
        int[][] nn_list; /* nearest neighbor list; contains for each node i a sorted list of n_near nearest neighbors */
        int[][] nn_list_all; /* nearest neighbor list; contains for each node i a sorted list of n_near nearest neighbors including the depot*/
    }

    static Problem instance;

    /**
     * 计算 candidate list（其中的城市均为可访问城市）
     * computes nearest neighbor lists of depth nn for each city
     *
     * @return result[i][j][k]
     * i=0返回m_nnear（不包括仓库）；i=1返回m_nnear_all（包括仓库）
     * j代表当前城市，result的值代表下一个城市的编号，k代表当前城市到下一个城市的顺序索引
     * result[0][1][3] = 5：不包括仓库，城市1的第3个临近城市为城市5
     */
    static int[][][] compute_nn_lists() {

        //但是，这里面计算的城市序列并不全是可访问城市序列，是所有城市的城市序列

        int i, node, nn, count1, count2;
        // 几个临时存储距离的数组
        int size = VRPTW.n;
        double[] distance_vector = new double[size + 1];
        int[] help_vector = new int[size + 1];

        // nn表示，邻近城市列表中，当前城市的邻近城市的个数
        nn = Ants.nn_ants;
        if (nn >= size + 1) nn = size - 2;
        Ants.nn_ants = nn;

        int[][][] result = new int[2][][];
        int[][] m_nnear = new int[size + 1][nn]; // exclude the depot city
        int[][] m_nnear_all = new int[size + 1][nn]; // include also the depot city

        /* compute candidate-sets for all nodes */
        for (node = 0; node < size + 1; node++) {
            for (i = 0; i < size + 1; i++) {
                /* Copy distances from nodes to the others */
                distance_vector[i] = VRPTW.instance.distance[node][i];
                help_vector[i] = i;
            }
            distance_vector[node] = Integer.MAX_VALUE; // 自己到自己
            Utilities.sort2(distance_vector, help_vector, 0, size);

            // exclude the depot city
            count1 = 0;
            i = -1;
            while (count1 < nn) {
                i++;
                if (help_vector[i] != 0) {
                    m_nnear[node][count1] = help_vector[i];
                    count1++;
                } else {
                    continue;
                }
            }

            // include also the depot city
            count2 = 0;
            i = -1;
            while (count2 < nn) {
                i++;
                if (help_vector[i] != 0) {
                    m_nnear[node][count2] = help_vector[i];
                    count2++;
                } else {
                    continue;
                }
            }
        }

        // 返回值
        result[0] = m_nnear;
        result[1] = m_nnear_all;
        return result;
    }

    /* FUNCTION: the following four functions implement different ways of computing distances for TSPLIB instances */
    /* INPUT: two node indices */
    /* OUTPUT: distance between the two nodes */
    // 对x向下取整
    static double dtrunc(double x) {
        int k;
        k = (int) x;
        x = (double) k;
        return x;
    }

    // [欧氏距离] compute Euclidean distances between two nodes rounded to next integer for TSPLIB instances
    static double euclidianDistance(int i, int j) {
        double xd = 0, yd = 0;
        xd = VRPTW.instance.nodes[i].x - VRPTW.instance.nodes[j].x;
        yd = VRPTW.instance.nodes[i].y - VRPTW.instance.nodes[j].y;
        double r = Math.sqrt(xd * xd + yd * yd);
        return r;
    }

    // [欧氏距离向上取整] compute ceiling distance between two nodes rounded to next integer for TSPLIB instances
    static int ceil_distance(int i, int j) {
        double xd = instance.nodes[i].x - instance.nodes[j].x;
        double yd = instance.nodes[i].y - instance.nodes[j].y;
        double r = Math.sqrt(xd * xd + yd * yd);
        return (int) Math.ceil(r); // 向上取整
    }

    // [计算地球两个坐标之间弧面距离，利用经纬度]
    // compute geometric distance between two nodes rounded to next integer for TSPLIB instances
    static int geo_distance(int i, int j) {
        double deg, min;
        double lati, latj, longi, longj;
        double q1, q2, q3;
        int dd;
        double x1 = instance.nodes[i].x, x2 = instance.nodes[j].x, y1 = instance.nodes[i].y, y2 = instance.nodes[j].y;

        deg = dtrunc(x1);
        min = x1 - deg;
        lati = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;
        deg = dtrunc(x2);
        min = x2 - deg;
        latj = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;

        deg = dtrunc(y1);
        min = y1 - deg;
        longi = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;
        deg = dtrunc(y2);
        min = y2 - deg;
        longj = Math.PI * (deg + 5.0 * min / 3.0) / 180.0;

        q1 = Math.cos(longi - longj);
        q2 = Math.cos(lati - latj);
        q3 = Math.cos(lati + latj);
        dd = (int) (6378.388 * Math.acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
        return dd;
    }

    // compute ATT(Average Travel Time) distance between two nodes rounded to next integer for TSPLIB instances
    static int att_distance(int i, int j) {
        double xd = instance.nodes[i].x - instance.nodes[j].x;
        double yd = instance.nodes[i].y - instance.nodes[j].y;
        double rij = Math.sqrt((xd * xd + yd * yd) / 10.0);
        double tij = dtrunc(rij);
        int dij;

        if (tij < rij)
            dij = (int) tij + 1;
        else
            dij = (int) tij;
        return dij;
    }

    /**
     * 计算所有城市的距离矩阵
     * computes the matrix of all intercity/inter customers distances
     *
     * @param scalingValue
     * @return
     */
    static double[][] compute_distances(double scalingValue) {
        int i, j;
        int size = VRPTW.n; // 不包含仓库
        // include also the depot city in the distance matrix: it will correspond to index 0 for row and column
        double matrix[][] = new double[size + 1][size + 1];
        for (i = 0; i < size + 1; i++) {
            for (j = 0; j < size + 1; j++) {
                if (InOut.distance_type == InOut.Distance_type.ATT) {
                    matrix[i][j] = att_distance(i, j);
                } else if (InOut.distance_type == InOut.Distance_type.CEIL_2D) {
                    matrix[i][j] = ceil_distance(i, j);
                } else if (InOut.distance_type == InOut.Distance_type.EUC_2D) {
                    matrix[i][j] = euclidianDistance(i, j);
                    if (scalingValue != 0) {
                        matrix[i][j] *= scalingValue;
                    }
                } else if (InOut.distance_type == InOut.Distance_type.GEO) {
                    matrix[i][j] = geo_distance(i, j);
                }
            }
        }
        return matrix;
    }

    /* 计算路径t的长度（未回到仓库）*/
    static double compute_tour_length(ArrayList<Integer> t) {
        int i;
        double sum = 0;
        if (t.size() > 1) {
            for (i = 0; i < t.size()-1; i++) {
                sum += VRPTW.instance.distance[t.get(i) + 1][t.get(i + 1) + 1];
            }
        }
        return sum;
    }

    /* 计算路径t的长度（从仓库出发，并回到仓库） */
    static double compute_tour_length_(ArrayList<Integer> t) {
        int i;
        double sum = 0;

        if (t.size() > 1) {
            sum += VRPTW.instance.distance[0][t.get(1) + 1];
            for (i = 1; i < t.size() - 2; i++) {
                sum += VRPTW.instance.distance[t.get(i) + 1][t.get(i + 1) + 1];
            }
            sum += VRPTW.instance.distance[t.get(t.size() - 2) + 1][0];
        }

        return sum;
    }


    public void setNoVehicles(int noVehicles) {
        this.noVehicles = noVehicles;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public void setRequests(ArrayList<Request> requests) {
        this.requests = requests;
    }

    public ArrayList<Request> getRequests() {
        return requests;
    }

    public void setIdAvailableRequests(ArrayList<Integer> idAvailableRequests) {
        this.idAvailableRequests = idAvailableRequests;
    }

    public ArrayList<Integer> getIdAvailableRequests() {
        return idAvailableRequests;
    }

    public void setDynamicRequests(ArrayList<Request> dynamicRequests) {
        this.dynamicRequests = dynamicRequests;
    }

    public ArrayList<Request> getDynamicRequests() {
        return dynamicRequests;
    }

    public int getCapacity() {
        return capacity;
    }
}
